package finalPrices;

import java.util.Stack;

public class Solution {
    public int[] finalPrices(int[] prices) {
        // 思路 题目意思为找右边第一个比prices[i]小的元素
        int[] discounts = getDiscounts(prices);
        for (int i = 0; i < prices.length; i++) {
            discounts[i] = prices[i] - discounts[i];
        }
        return discounts;
    }
    private int[] getDiscounts(int[] prices){
        Stack<Integer> stack = new Stack<>();
        int[] discounts = new int[prices.length];
        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty()&&prices[stack.peek()]>prices[i]){
                discounts[stack.peek()] = prices[stack.pop()] - prices[i];
            }
            stack.push(i);
        }
        return discounts;
    }
}
